#include <iostream>
using namespace std;

static int count = 0;
void quickSort(int arr[], int left, int right)
{
          int i = left, j = right;
          int tmp;
          int pivot = arr[(left + right) / 2];

      /* partition */
      while (i <= j)
      {
            while (arr[i] < pivot)
            {
                  i++;
                  count++;
            }
            while (arr[j] > pivot)
            {
                  j--;
                  count++;
            }
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
            count++;
      };

      /* recursion */
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
      {
          quickSort(arr, i, right);
      }
}

int main()
{
    int array[] = {1,5,8,3,6,7,4,9,2};
    int size = sizeof (array) / sizeof(int);
    quickSort(array, 0, size - 1);
    for(int i = 0; i < size; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl << count << endl;
}
